#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define mes(x) memset(x,0,sizeof(x))
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout)

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int MAXN = 1e5+10;
const int MAXS = 1<<12;
const int mod = 1e9+1;

void add(ll &x,ll y){x = (x+y) % mod;}

int n;
ll f[2][MAXS],ans = 1;
bool v[MAXN];
int mat[22][22],lim[22],num[22],en;

void solve(int x){
	for(int i = 1;i <= 18;i++){
		if(i == 1) mat[i][1] = x;
		else mat[i][1] = mat[i-1][1] * 2; if(mat[i][1] > n) break; v[mat[i][1]] = 1; en = i; num[i] = 1;
		for(int j = 2;j <= 12;j++) {mat[i][j] = mat[i][j-1] * 3; if(mat[i][j] > n) break;v[mat[i][j]] = 1;num[i]++;}
		lim[i] = 1 << num[i];
	} int o = 0; ll tot = 0;
	for(int i = 0;i < lim[1];i++) if(!(i & (i << 1))) f[o][i] = 1;
	for(int i = 2;i <= en;i++,o ^= 1){
		for(int s = 0;s < lim[i];s++){
			f[o^1][s] = 0;
			if(s & (s << 1)) continue;
			for(int k = 0;k < lim[i-1];k++){
				if(k & (k << 1)) continue;
				if(s & k) continue;
				if(!f[o][k]) continue;
				add(f[o^1][s],f[o][k]);
			}
		}
	}
	for(int i = 0;i < lim[en];i++) add(tot,f[o][i]);
	ans = ans * tot % mod;
}

int main (){
	n = in;
	for(int i = 1;i <= n;i++) if(!v[i]) solve(i);
	printf("%lld\n",ans % mod);
	return 0;
}

